package com.demo.work;

import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

import static com.demo.util.FileUtil.readTxt;

/**
 * @program: ssm_demo
 * @author: Mr.Zhuo
 * @create: 2022-04-12 14:41
 **/
public class Trie {

    /**
     * 使用前缀树来实现索引创建
     * @param args
     */
    public static void main(String[] args) throws Exception {
        Trie trie = new Trie();

        // 读取文件
        String filePath = "d:\\baidu.txt";
        String readTxt = readTxt(filePath);
        // 取得每个单个词
        String[] strings = readTxt.split(":");
        for (String string : strings) {
            trie.add(string);
        }
        System.out.println("请输入要查找的词：");
        Scanner scanner = new Scanner(System.in);

        String nextLine = scanner.next();

        if (trie.contains(nextLine)){
            System.out.println("存在");
        }else {
            System.out.println("不存在");
        }
    }
    // 节点类
    private class Node {
        public Boolean isWord;
        public HashMap<Character, Node> next;
        public Node(Boolean isWord) {
            this.isWord = isWord;
            next = new HashMap<>();
        }
        public Node() {
            this(false);
        }
    }

    private Node root;
    private int size;

    public Trie() {
        root = new Node();
        size = 0;
    }

    // 获取Trie中储存的单词个数
    public int size() {
        return size;
    }

    // 向Trie中插入一个单词
    public void add(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }
            cur = cur.next.get(c);
        }
        if (!cur.isWord) {
            cur.isWord = true;
            size ++;
        }
    }

    // 从 Trie 中删除某个单词
    public void delete(String word) {
        if (!contains(word)) return;
        Stack<Node> stack = new Stack<>();
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            cur = cur.next.get(c);
            stack.push(cur);
        }
        cur.isWord = false;
        int index = word.length() - 1;
        while (!stack.empty() && !stack.peek().isWord && stack.peek().next.isEmpty()) {
            stack.pop();
            stack.peek().next.remove(word.charAt(index--));
        }
        size --;
    }

    // 查询某个单词
    public boolean contains(String word) {
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }

    // 判断是否有单词是以某个单词为前缀
    public boolean isPrefix(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null) {
                return false;
            }
            cur = cur.next.get(c);
        }
        return true;
    }

    // 模式匹配 通配符 ‘.’
    public boolean match(String pattern) {
        return match(root, pattern, 0);
    }

    private boolean match(Node node, String pattern, int index) {
        if (index == pattern.length()) {
            return node.isWord;
        }
        char c = pattern.charAt(index);
        if (c != '.') {
            if (node.next.get(c) == null) return false;
            return match(node.next.get(c), pattern, index + 1);
        }
        for (char nextChar : node.next.keySet()) {
            if (match(node.next.get(nextChar), pattern, index + 1)) return true;
        }
        return false;
    }



}
